//
// 搜索二维矩阵 II
// Created by madison on 2022/9/13.
//


#include "vector"

using namespace std;

class Solution {
public:
    // 方法一：直接查找
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        for (const auto &row: matrix) {
            for (int element: row) {
                if (element == target) {
                    return true;
                }
            }
        }
        return false;
    }

    // 方法二：二分查找
    bool searchMatrix1(vector<vector<int>> &matrix, int target) {
        for (const auto &row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }

    // 方法三：Z 字形查找
    bool searchMatrix2(vector<vector<int>> &matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            } else {
                ++x;
            }
        }
    }
};

int main() {
    vector<vector<int>> matrix = {{1,  4,  7,  11, 15},
                                  {2,  5,  8,  12, 19},
                                  {3,  6,  9,  16, 22},
                                  {10, 13, 14, 17, 24},
                                  {18, 21, 23, 26, 30}};

    Solution solution;
    printf("%d\n", solution.searchMatrix(matrix, 5));
    printf("%d\n", solution.searchMatrix1(matrix, 20));
    printf("%d\n", solution.searchMatrix2(matrix, 5));

    return 0;
}